In typical database systems, users store, update and retrieve information by submitting commands or statements to a database application. To be correctly processed, the statements must comply with the database language that is supported by the database application. One popular database language is known as Structured Query Language (SQL).
A logical unit of work that is comprised of one or more database language statements is referred to as a transaction. When multiple users share a database system, it is impractical to allow only one transaction to execute at a time. However, when many transactions are allowed to execute at the same time, the issue of consistency arises. Transactional database management systems provide a special statement--"commit"--which a user or program submits to delineate the statements that make up a transaction.
To ensure predictable and reproducible results, techniques have been developed which protect concurrently executing transactions from interacting with one another in uncontrolled ways. Transactions are designed to make database changes in such a way that the database, as a whole, moves from one consistent state to another.
Not only must transactions leave the database in a consistent state upon completion, but transactions must also see the database in a consistent state when they begin. This condition is difficult to satisfy because there may be concurrently executing transactions, each of which may be causing a temporary inconsistency visible only within that single transaction. Consequently, transactions must not be able to see the changes made by concurrently executing transactions until those transactions commit (i.e. terminate and make their changes permanent).
One approach to ensure that transactions do not see changes made by concurrently executing transactions is to prevent transactions from reading a data item that has been updated until the transaction that updated the data item commits. However, this approach reduces the concurrency in the system by causing transactions that wish to read data items (readers) to wait for transactions that have written to data items (writers) to commit.
An alternate approach to ensure that transactions see a consistent view of the database is to provide a mechanism that allows a reader transaction to see a version of the data item that does not include the updates made by any uncommitted transaction. However, in systems that provide a less-than-newest version of a data item, it is not always apparent which versions of a data item can and cannot be supplied to a transaction. Further, among those versions of a data item that can be supplied to a transaction, some versions will consume more overhead to supply than other versions.
Based on the foregoing, it is desirable to provide a mechanism for determining which versions of a data item may be supplied to a transaction. It is further desirable to provide a mechanism that selects the versions of data items to supply to transactions in a way that reduces the overhead required to supply the version of the data item. Specifically, it is desirable to select versions that require less overhead to construct, while still ensuring that the versions seen are recent enough.